package sorting;

/**
 * Insert Sort
 *  i=0
 *  [-1, 8, 4, 0, 7, 5, 3]
 *  key = -1 -- shift(-1)
 *  i=1
 *  [-1, 0, 8, 4, 7, 5, 3]
 *  key = 0 -- shift(0)
 *    
 *  
 * @author SamuelSantos
 *
 */
public class InsertionSort<T extends Comparable<T>> implements Sorting<T> {

	@Override
	public void sort(T[] array) {
		for (int i = 0; i < array.length; i++){
			int smallestIndex = smallest(i, array);
			
			//store the value
			T key = array[smallestIndex];
			
			int j;
			for (j=smallestIndex; j > i; j--){
				Util.swap(array,j, j-1);
			}
			
			while(less(array, key, j)){
				Util.swap(array, j, j-i);
			}
			array[j] = key;
		}
	}
	
	 /**
     * Find the smallest element into the array.
     * 
     * @param beginIndex the index of begin search.
     * @param array an array 
     * 
     * @return the position of the smallest value.
     */
    public int smallest(int beginIndex , T[] array){
            int smallestIndex = beginIndex;
            for(int i = beginIndex + 1; i< array.length; i++){
                    if (array[i].compareTo(array[smallestIndex]) < 0){
                            smallestIndex = i;
                    }
            }
            return smallestIndex;
    }
	
    /**
     * Compare two element and return if x is less than y.
     * Then y is greater than x.
     * 
     * @param array an array
     * @param x an index of the array
     * @param y an other index of the array
     * 
     * @return true or false
     */
    public boolean less(T[]array, T key, int index){
            return (array[index].compareTo(key) > 0); 
    }
    
}













